#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode* next;
}LNode; // 队列节点

typedef struct{
    LNode* front; // 头指针
    LNode* rear; // 尾指针
}LkQueue;

void initQueue(LkQueue* Q); // 初始化队列
bool isEmpty(LkQueue* Q); // 判断队列是否为空
bool enQueue(LkQueue* Q, ElemType value); // 进队操作
bool deQueue(LkQueue* Q, ElemType* value); // 出栈操作
bool getHead(LkQueue* Q, ElemType* value); // 获取队头元素,但是不出队

int main()
{
    LkQueue* Q = (LkQueue*) malloc(sizeof(LkQueue));
    initQueue(Q);
    for(int i = 1; i < 10; i++)
    {
        enQueue(Q, i);
    }
    ElemType data; 
    getHead(Q, &data);
    printf("head: %d\n", data);
    while(!isEmpty(Q))
    {
        deQueue(Q, &data);
        printf("%d ", data);
    }
    printf("\n");
    return 0;
}

void initQueue(LkQueue* Q)
{
    Q->front = Q->rear = (LNode*)malloc(sizeof(LNode)); // 创建头结点
    Q->front->next = NULL;
}

bool isEmpty(LkQueue* Q)
{
    return (Q->front == Q->rear);
}

bool enQueue(LkQueue* Q, ElemType value)
{
    LNode* node = (LNode*)malloc(sizeof(LNode));
    if(node == NULL)
    {
        printf("node creation failed\n");
        return false;
    }
    node->data = value;
    node->next = NULL;
    Q->rear->next = node;
    Q->rear = node;
}

bool deQueue(LkQueue* Q, ElemType* value)
{
    if(isEmpty(Q))
    {
        printf("Queue is Empty\n");
        return false;
    }
    LNode* temp = Q->front->next;
    *value = temp->data;
    Q->front->next = temp->next;
    if(Q->rear == temp) // 说明此链表只有一个元素，需要修改尾指针
    {
        Q->rear = Q->front; // 指向头结点
    }
    free(temp);
    return true;
}

bool getHead(LkQueue* Q, ElemType* value)
{
    if(isEmpty(Q))
    {
        printf("Queue is Empty\n");
        return false;
    }
    *value = Q->front->next->data;
    return true;
}